package graph.搜索算法;

/**
 * 二叉树的DFS遍历实现
 * 采用递归和非递归两种方式实现
 */

import 搜索算法.DFS;

import javax.swing.plaf.basic.BasicTreeUI;
import java.util.Stack;

/**
 * 定义树的节点类
 */
@SuppressWarnings("all")
class TreeNode{
    int value; // 节点的值
    TreeNode left; // 左孩子指针
    TreeNode right; // 有孩子指针

    public TreeNode(int value) {
        this.value = value; // 其他指针默认的初始化为null
    }
}

/**
 * 定义二叉树
 */
@SuppressWarnings("all")
class BinaryTree{
    private TreeNode root; // 树的根节点

    public BinaryTree(TreeNode treeNode) {
        this.root = treeNode; // 初始化根节点
    }

    /**
     * 递归实现DFS算法 等同于树的中序遍历  root---left---right
     * @param curroot：当前根节点
     */
    public void TreeDFS_recursion(TreeNode curroot) {
        if (curroot == null) {
            return;
        }
        System.out.println(curroot.value);
        TreeDFS_recursion(curroot.left);
        TreeDFS_recursion(curroot.right);
    }

    /**
     * 费递归实现DFS算法  利用栈结构实现
     */
    public void TreeDFS_not_recursion(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>(); // 定义栈
        stack.push(root); // 初始化让root节点入栈
        while (!stack.isEmpty()) { // 当栈为空时，循环退出
            TreeNode top = stack.pop(); // 弹出当前栈顶节点
            System.out.print(top.value+" "); // 直接出栈
            // 注意栈是先进后出，此时先入栈的应该是右节点，其次是左节点
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
    }

}


public class Q1_TreeDFS {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        BinaryTree binaryTree = new BinaryTree(root); // 初始化一颗树
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(5);
        TreeNode treeNode5 = new TreeNode(6);
        root.left = treeNode1;
        root.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode4.left = treeNode5;
        binaryTree.TreeDFS_not_recursion(root);
    }
}
